package com.zhaofan.other;

import org.junit.Test;

import java.net.Socket;
import java.util.Arrays;
import java.util.LinkedList;

public class No42 {

    @Test
    public void test() {
        int[] arr = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(trap(arr));
    }

    @Test
    public void test1() {
        System.out.println((2 < 3));
    }

    public int trap(int[] height) {
        if (height.length < 3) {
            return 0;
        }
        int result = 0;
        LinkedList<Integer> stock = new LinkedList<>();
        for (int i = 0; i < height.length; i++) {
            //入栈条件:栈顶元素小于i,i+1<1
            while (!stock.isEmpty() && height[i] > height[stock.peek()]) {
                int top = stock.pop();
                if (stock.isEmpty()) {
                    break;
                }
                int left = stock.peek();
                int currentHeight = Math.min(height[i], height[left]) - height[top];
                result += (i - left - 1) * currentHeight;
            }
            stock.push(i);
        }
        return result;
    }
}
